package array;

/**
 * @Author Yi Jun jie
 * @Date 2021/3/1 16:50
 * 4. 寻找两个正序数组的中位数
 */
public class LeetCode4 {
    public static void main(String[] args) {
        int[] nums1 = {1,3,4,6,7}, nums2 = {2,5,8,10};
        System.out.println(new Solution4().findMedianSortedArrays(nums1, nums2));
    }
}

//执行用时：3 ms,在所有 Java 提交中击败了82.35%的用户 (效率算是一般)
class Solution4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //合并数组(这里每个数组都是从小到大排列的)
        int l1 = nums1.length, l2 = nums2.length, i = 0, j = 0, k = 0;
        int[] nums = new int[l1 + l2];//先确定数组的长度大小
        while (i < l1 && j < l2) {
            if(nums1[i] > nums2[j]) nums[k++] = nums2[j++];
            else nums[k++] = nums1[i++];
        }
        while (i < l1) nums[k++] = nums1[i++];
        while (j < l2) nums[k++] = nums2[j++];
        //判断是奇偶
        int numsNum = nums.length;
        double midNum;
        //如果是偶数
        if(numsNum % 2 == 0) {
            midNum = (nums[numsNum/2] + nums[numsNum/2 - 1]) / 2.0;
        //否则是奇数
        } else {
            midNum = nums[numsNum/2];
        }
        return midNum;
    }
}
